1. Field of the Invention
The present invention relates generally to image smoothing, and more particularly to triangulation based raster image interpolation.
2. Related Art
A raster image is a representation of a scene made out of pixels. Each pixel represents a small area of the image, and its content is uniform: it is characterized by a size, a position, and a color.
The resolution of a raster image is defined as the number of pixels it contains. For two images that represent the same scene, the image with the larger number of pixels is the one with the higher resolution, and therefore is also the one that has the smaller pixels. Small pixels mean that smaller details in the scene can be observed.
All raster images have a limited resolution. Higher end cameras and/or film generally produce higher resolution images than low-end ones. Over the years, technological advances in the field of digital cameras have enabled the creation of images with a progressively increasing resolution.
Generally, photographs are taken at the distance and zoom level required for the application. For instance, a landscape image to be published in a magazine is usually taken using a high-end, high-resolution camera. This way, the quality of the image will be sufficiently high for the demanding publishing quality requirements of the magazine. However, there are cases when the resolution of an image is not sufficient, even if it is very high. For instance, if an image is magnified to show some of its details, there comes a point when magnifying does not show more details but instead shows the individual pixels of the image bigger. The shape and size of individual pixels become very apparent in areas where there is a strong difference in color and/or intensity: a “staircase” effect becomes visible. Images with a higher resolution allow for more magnification before that effect becomes visible on oblique linear features.
Sometimes, it is required to display an image at a scale that is too high with respect to the resolution of that image. For instance, this is the case when creating a mosaic of old and recent aerial images, or when combining images taken by various types of cameras: all images have to be displayed at the same scale to represent terrain correctly. However, all images do not necessarily have the same resolution. The lower resolution ones may then appear with apparent pixels in them. Sometimes, such low-resolution images are the only data available for the area of the scene to be displayed, and cannot be replaced. In such cases, a method for changing the appearance of the image is required to improve its look at high magnification levels.
One class of methods is based on pixel interpolation. These methods consist of generating a new image that has the same size as the original image, but at the required higher resolution. Each pixel of the new image is set to a color that is the result of an interpolation between the colors of the closest pixels at the corresponding location in the original image.
Several types of interpolation functions are available, out of which 2 are commonly used in imaging applications: bilinear and bicubic. The bilinear interpolation function is simple (and therefore fast) to calculate. The color of each pixel in the new image is the result of a linear interpolation between the colors of the surrounding pixels in the original image. The bicubic function is more complex (and therefore takes more time) to calculate, as more pixels are considered in more complex calculations. However, the results obtained with the bicubic interpolation function are better than with the bilinear function.
Both interpolation methods are efficient at making the shape and size of individual pixels harder to see. However, although the bicubic interpolation method provides a clearer image than the linear interpolation method, both methods still show the “staircase” effect on oblique linear features.
Another class of methods is based on image reconstruction. An example of a method using image reconstruction is described in X. Yu, B. S. Morse and T. W. Sederberg, “Image reconstruction using data-dependent triangulation”, IEEE Computer Graphics and Applications, vol. 21, no. 3, 2001, pp. 62-68 (hereinafter “Yu”), incorporated herein by reference. These methods consist of fitting a continuous surface function through image pixels. One of those methods is based on data-dependent triangulation. It consists of creating a triangulation out of the pixels of the image: the vertices of each triangle are located in the center of a pixel of the image. Then, the method creates new triangles by swapping edges between adjacent triangles, aiming to minimize the value of a cost function that calculates the difference between the orientation of the triangle edges with the orientation of the image gradients.
Data-dependent triangulation involves the creation of a triangulation that covers the area of the image to be displayed. Data-dependent triangulation may generally have two main steps: creation of a basic triangulation, and optimization of the triangulation.
Creation of a Basic Triangulation
This step is illustrated in FIGS. 1A-D. A basic triangulation is created, based on the size and number of pixels of the original image (1A). The triangulation (1B) is composed of a set of right triangles, each triangle vertex being located exactly in the center of a pixel of the image. Each triangle vertex is then assigned the color of its corresponding pixel (1C). The result of such a basic triangulation, which creates an interpolated version of the original image (1A), can be displayed using standard graphics libraries, such as OpenGL. The result is a continuous tone image (1D).
Optimization of the Triangulation
Then the triangulation may be optimized in such a way that it better represents the image being interpolated. For instance, in the interpolated image in FIG. 1D, triangle edges appear as linear features that are vertical, horizontal or oblique. It is possible to rearrange the triangles in such a way that would make some of their edges parallel to the image gradients, and therefore creating a smoother interpolated image. Possible arrangements for two triangles that form a quadrilateral are illustrated in FIGS. 2A and 2B. Two adjacent triangles T1 and T3 that form a quadrilateral are illustrated in FIG. 2A. Two different triangles T2 and T4 that form the same quadrilateral are shown in FIG. 2B. Both ways are acceptable: they both cover the entire area of the quadrilateral, they both produce two non-degenerate triangles, and interpolate colors between the four vertices v1, v2, v3 and v4. However, if there is a strong color gradient in the area of those four vertices, then one may better reproduce the gradient than the other.
Data-dependent triangulation uses a cost function to evaluate which of the two configurations better represents the color gradient. For instance, suppose the quadrilateral formed by vertices v1, v2, v3 and v4 is as shown in FIG. 2A. The cost of this configuration is compared with the cost of an alternate configuration, e.g., the one in FIG. 2B. If the cost of configuration 2B is lower than the cost of configuration 2A, then the two triangles T1 and T3 are replaced by new triangles T2 and T4. This process is called an “edge swap”.
The cost of a triangle configuration may be calculated as follows. If the three vertices of a triangle form a plane in three dimensions (3D), where the x and y coordinates are the location of the vertices, and the z coordinate is the color intensity at the location of those vertices, the equation of an interpolating linear function for triangle i is:Pi=aix+biy+ci Then, the cost is calculated as:Cost=∥∇P1∥∇P3∥−∇P1·∇P3  (C1)where∥∇Pi∥=√{square root over (ai2+bi2)} (∇ being the gradient operator).
This cost function (C1) favors triangle edges that are parallel to the image color intensity contour lines (in RGB color space). Color intensity contour lines are analogous to geographic contour lines that trace areas of the same elevation on a map. Color intensity contour lines are contour lines that trace areas of the image that have the same color intensity. The method is applied sequentially to each set of two adjacent triangles in the triangulation, as long as the two triangles form a convex quadrilateral (and not a triangle). When all the triangles of the triangulation have been visited, the method is applied again to the whole triangulation until the overall cost of the whole triangulation does not decrease, or after a fixed number of iterations.
The method is illustrated in FIGS. 3A-H. For each set of two adjacent triangles in the triangulation that form a convex shape and that is not a triangle, a check is made whether these two triangles generate a higher cost than if their common edge was swapped. If swapping the triangles produces a lower cost, then the common edge is swapped. The original image is shown in 3A. In 3B, a basic triangulation is produced. In 3C, the edge between the first two triangles on the top left is swapped because doing so lowers the cost. In 3D, the edge between the next set of two triangles is also swapped. In 3E, another edge is swapped. The process is continued until all sets of two triangles have been visited, in 3F. Then, in another iteration, more sets of two triangles can be visited and their edges swapped, as in 3G. When the iteration process does not decrease the cost anymore, the resulting image is produced out of the interpolation, in 3H. The image in 3H is much smoother than the original image 3A, and also smoother than the one resulting from the un-optimized triangulation shown in FIG. 1D. The staircase effect, while still apparent in FIG. 1D, is absent from 3H.
Data-dependent triangulation adds an extra optimization step to the method. If an edge swap decreases the cost of the triangle configuration, then the swap is done. On the other hand, if the edge swap does not decrease (or if it actually increases) the cost of the configuration, then the method checks whether if the edge swap was done regardless of the increase in cost, whether that swap in combination with edge swaps of the two newly formed triangles with their neighbor triangles would actually lower the overall cost even more than if the edge swap was not done. If this is the case, then the edge swap is done in spite of the fact that it increases the cost.
Apart from some wrongly-oriented triangles, the triangulation-based method is better than the interpolation-based methods to remove staircase effects. However, the method has at least the following disadvantages.
First, the triangulation-based method is based on color intensity only. When the method tries to decide how to swap edges of two adjacent triangles, it calculates a cost value based on pixel color intensity only. In several cases, different colors have the same intensity. In such cases, the method may not make the right decision, and triangles may be wrongly oriented.
Second, the triangulation-based method does not work properly on thin lines and cannot remove the staircase effect along them.
Third, the triangulation-based method generates long parallel lines along some gradients, making them appear unnatural. This is particularly obvious along oblique strong gradients, and along very soft gradient areas.
Fourth, when used on images that show objects with tight curves, the curves are not properly approximated by the triangulation-based method, being represented by triangles that are often too long.
Fifth, triangles are sometimes generated in such a way that they cross areas where the colors differ greatly from the interpolated color of those triangles. Such areas are striking as they break the smooth uniformity of the image.
Sixth, the triangulation-based method is slow to execute. The amount of processing required for an image to be triangulated and optimized is high, and consequently the time required for applying the method on an image is also long.
What is needed is an improved method of changing the appearance of images visualized at a high magnification level, in such a way that the individual pixels are not apparent and give the impression that the image has a higher resolution.